package com.learn.algorlthm;

/**
 * @classname:
 * @Description: 打印从1到最大的n位数
 * @author: yfpu(fengpu.yang @ ucarinc.com)
 * @Date: 2018-07-16 19:20
 * 题目描述：
 *  输入数字n，按顺序打印出从1最大的n位十进制。比如输入3，则打印出1、2、3一直到最大的3位数即999.
 */
public class Learn17 {

    /**
     * 解题思路
     * 由于n可能会非常大，因引不能直接用int表示数字，而是用char数组进行存储。
     * 使用回溯法得到所有的数
     */

    public static void print1ToMaxOfNDigits(int n) {
        if (n <= 0)
            return;
        char[] number = new char[n];

        print1ToMaxOfNDigits(number, -1);

    }

    private static void print1ToMaxOfNDigits(char[] number, int digit) {

        if (digit == number.length - 1) {
            printNumber(number);
            return;
        }

        for (int i = 0; i < 10; i++) {
            number[digit + 1] = (char)(i + '0');
            print1ToMaxOfNDigits(number, digit + 1);
        }
    }

    private static void printNumber(char[] number) {
        int index = 0;
        while (index < number.length && number[index]== '0')
            index++;
        while (index < number.length)
            System.out.print(number[index++]);
        System.out.println();
    }

}
